1. Field of the Invention
The present invention relates generally to databases and, more particularly, to query optimization in a database.
2. Description of the Background Art
Databases commonly organize data in the form of tables, each table having a number of rows and columns. Each row in a table generally has a data value associated with each of the columns, this intersection of rows and columns commonly called a cell. A system needing access to data in the database typically issues a request in the form of a query. A query usually involves a request for the data contained in one or more cells of any rows which meet a particular condition. This condition often involves the comparison of the values of cells in a column to some other value to determine whether the row associated with the compared cell meets the condition.
A direct comparison of each cell of interest in a table to a value is often computationally expensive, and database developers have accordingly introduced means by which rows meeting a comparison operation can be more readily determined without the need to traverse every row of a table. A typical optimization involves the use of a tree structure to determine which rows contain a desired value. Each node of the tree represents a different value appearing within a particular column in any row of the table. Each node comprises a bitmap indicating that particular rows corresponding to each bit of the bitmap have the value in the particular column.
This approach is reasonably efficient when an exact value is desired, such as with, for example, a query for all rows in which a particular column has the integer value ‘5’. In this approach, database software would traverse the tree structure to locate the node corresponding to the integer value of ‘5’ and retrieve an associated bitmap. The rows for which the value of the particular column is ‘5’ would be represented by “set” bits in the bitmap (i.e., bits set to either a ‘0’ or a ‘1’ value in order to indicate that a corresponding row meets the condition). As a result, the database software is able to simply retrieve those rows and produce a result set from them.
However, this approach does not provide an optimal solution for more complex operations. For example, it is sometimes necessary to process a query for all rows in which the value of a particular column is within a range of values. Using the aforementioned approach, it would be necessary to determine what possible values are within the range, traverse the tree to obtain the bitmap for each individual value within the range, and perform an “and” operation on each of the resulting bitmaps to obtain a final result bitmap. This operation is particularly inefficient for large value ranges, and requires a large number of traversals through the tree.
Accordingly, what is desired is a means of efficiently processing queries that comprise range conditions.